package com.yudylaw.algorithm;

public class Shell {

	/**
	 * insert sort 演变而来
	 */
	public static void main(String[] args) {
		int[] nums = {2,10,12,3,1,8,20,23,100,13,9,5,0};
		shellSort(nums);
		for(int k=0;k<nums.length;k++){
			System.out.print(nums[k]+",");
		}
	}
	
	public static void shellSort(int [] nums){
		int inner,outer;
		int temp;
		int h = 1;
		while(h <= nums.length/3)
			h = h*3 + 1;
		while(h>0){//步长移动
			for(outer = h;outer<nums.length;outer++){//insert sort
				temp = nums[outer];
				inner = outer;
				while(inner>h-1 && nums[inner-h] >=temp){
					nums[inner] = nums[inner-h];
					inner -=h;
				}
				nums[inner] = temp;
			}
			h = (h - 1)/3;
		}
	}
}
